package com.ifreeee.sort.quicksort;
import com.ifreeee.sort.InsertionSort;
import com.ifreeee.sort.ShellSort;
import com.ifreeee.sort.quicksort.stack.LinkedStack;
import com.ifreeee.sort.quicksort.stack.LinkedStackNode;
import com.ifreeee.utils.RandomUtils;
import org.junit.Test;
import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序（挖坑填数）
 */
public class QuickSort {

    private static int isInsert = 7;//数组长度小于 isInsert 就使用插入排序
    /**
     * 分析：
     * 1）取基准数方法（保守）
     *     随机选取基准
     * 2）当待排序序列的长度分割到一定大小后，使用插入排序
     * 3）相等值的处理
     *     在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
     *     遇到相等的元素，先换到两端，最后再堆到一起
     * 4）不使用递归
     *     自己写一个栈，需要记录的数据都存在堆中，不用递归，避免大量浪费虚拟机栈的内存
     * @param arr
     */
    public static void quickSort(int[] arr)
    {
        int left, right, pivot, temp;//左索引、右索引、基准数（取随机下标）、挖坑的时候存下的临时变量
        int i, j;//辅助下标
        int m, n;//m之前的都是 基准数 相等的值，n之后的都是 基准数
        boolean b = true;//true 从后往前找 | false 从前往后找
        Random r = new Random();
        LinkedStack linkedStack = new LinkedStack();
        LinkedStackNode pop = new LinkedStackNode(0, arr.length - 1, RandomUtils.randomNum(0, arr.length - 1, r));
        while(pop != null){//栈内容，判断弹栈 是否为空
            //把相应的参数取出来
            left = pop.getLeft();
            right = pop.getRight();
            if(right - left < isInsert){//如果right - left < 7 则使用插入排序即可；最坏的情况 和 快排一样，最好的情况要 比 快排好
                InsertionSort.insertionSort(arr, left, right);//插入排序
            }else{//快速排序
                pivot = pop.getPivot();
                temp = arr[pivot];//把基准数放到临时变量temp
                arr[pivot] = arr[left];//此时 arr[left] 为坑，可以把比基准数 temp 小的值填入 arr[left]
                b = true;//初始化true 从后往前找
                i = left;//初始化辅助下标
                j = right;
                m = left;
                n = right;
                wkts:while(true){//循环挖坑填数，当i == j 则结束
                    if(b){//true 从后往前找，找比 temp 小的值，填入坑arr[i]；若遇到 等于 temp 的值，放到最末端
                        while (temp <= arr[j]){
                            if(i == j){break wkts;}//结束挖坑填数
                            //找相等的值
                            if(temp == arr[j]){//若遇到 等于 temp 的值，放到最末端
                                arr[j] = arr[n];
                                arr[n] = temp;
                                n -= 1;
                            }
                            j -= 1;
                        }
                        arr[i] = arr[j];//填入坑arr[i]
                    }else{// false 从前往后找， 找比 temp 大的值，填入坑arr[j]；若遇到 等于 temp 的值，放到最前端
                        while (temp >= arr[i]){
                            if(i == j){break wkts;}//结束挖坑填数
                            //找相等的值
                            if(temp == arr[i]){//若遇到 等于 temp 的值，放到最前端
                                arr[i] = arr[m];
                                arr[m] = temp;
                                m += 1;
                            }
                            i += 1;
                        }
                        arr[j] = arr[i];//填入坑arr[j]
                    }
                    b = !b;//取反
                }
                arr[i] = temp;//此时i == j 而arr[i] 是最后一个坑，把基准数 temp填进去
                pivot = i - 1 + left;//此时 j 和 pivot 已无用，就拿来处理与temp相等的值；i 不动
                for(j = left; j < m; j += 1){
                    arr[j] = arr[pivot - j];
                    arr[pivot - j] = temp;
                }
                pivot = i + 1 + right;
                for(j = right; j > n; j -= 1){
                    arr[j] = arr[pivot - j];
                    arr[pivot - j] = temp;
                }
                j = i - m + left - 1;//分析： i - 左端长度 - 1 ；  左端长度 = m - left ； 结论 i - (m - left) - 1
                if(j > left){
                    linkedStack.push(left, j , RandomUtils.randomNum(left, j , r));//参数压栈
                }
                j = i + right - n + 1;//分析： i + 右端长度 + 1 ；  右端长度 = right - n
                if(j < right){
                    linkedStack.push(j, right, RandomUtils.randomNum(j, right, r));
                }
            }
            pop = linkedStack.pop();//每次处理完后 弹栈
        }
    }



    /**
     * 快速排序测试
     */
    @Test
    public void test2(){
        Random r = new Random();//随机数对象
        int num1 = 0;//代码一的时间
        int num2 = 0;//代码二的时间
        int num3 = 0;//代码三的时间
        int len = 10000;//测试的数据量
        int time = 5;
        for(int j = 0;j < time;j += 1){
            //初始化操作
            int[] arr = new int[len];
            int[] arr1 = new int[len];
            int[] arr2 = new int[len];
            for(int i = 0; i < len; i += 1){
                int a =  r.nextInt(len);
                arr[i]  =  a;//
                arr1[i]  =  a;//
                arr2[i]  =  a;//三个数组数据相同
            }
            //希尔排序无需初始化准备
            long t1 = System.currentTimeMillis();
            //代码一
            QuickSort.quickSort(arr);
            long t2 = System.currentTimeMillis();
            //代码二
            ShellSort.shellSort(arr1);
            long t3 = System.currentTimeMillis();
            //代码三
            Arrays.sort(arr2);
            long t4 = System.currentTimeMillis();
            num1 += (t2 - t1);
            num2 += (t3 - t2);
            num3 += (t4 - t3);
            for(int i = 0; i < len; i += 1){
                if(arr[i] != arr1[i] || arr[i] != arr2[i]){
                    System.out.println("错误");
                }
            }
            System.out.println(Arrays.toString(arr));
            System.out.println(Arrays.toString(arr1));
            System.out.println(Arrays.toString(arr2));
        }

        System.out.println("数据量：" + len + "\n测试次数：" + time);
        System.out.println("快速排序 耗时：" + num1 + "\n希尔排序 耗时：" + num2 + "\nTimSort排序 耗时：" + num3);
        /*
            数据量：10000000
            测试次数：5
            快速排序 耗时：5767
            希尔排序 耗时：10518
            TimSort排序 耗时：3921

            数据量：100000000
            测试次数：3
            快速排序 耗时：39881
            希尔排序 耗时：93445
            TimSort排序 耗时：26342

            结论：快速排序经过各种优化，脑袋写开花，还是比不上TimsSort，看来只有基数排序和堆排序有希望了
            改进：已改进
        */
    }

}
